<html>

<head>
<title>Components of a Bitmap</title>
</head>

<body>

<center>
<h1>CEOI 2001 Day 2 Problem 1</h1>
<h1>Components of a Bitmap</h1>
</center>

    <p ALIGN="JUSTIFY">Black and white pictures are
    usually stored as bitmaps. A <i>bitmap</i> is a rectangular grid of pixels.</p>
    <p ALIGN="JUSTIFY">A <i>polyline</i> between
    pixels <b><i>P</i></b> and <b><i>Q</i></b> is a sequence of black pixels <b><i>P=P<sub>1</sub>,
    P<sub>2</sub>, &#8230;, P<sub>k</sub>=Q</i></b>, where <b><i>P<sub>i</sub></i></b>
    and <b><i>P<sub>i+1</sub></i></b> (<i>i</i>=1, &#8230;, <i>k-1</i>) are
    (vertically or horizontally) adjacent pixels. A polyline <b><i>P<sub>1</sub>,
    P<sub>2</sub>, ..., P<sub>k</sub></i></b> is <i>closed</i> if <b><i>P<sub>1</sub></i></b>=<b><i>P<sub>k</sub></i></b>,
    and <b><i>P</i></b><i><sub>i &lt;&gt;</sub><sub> </sub><b>P</b><sub>j</sub></i>
    (<i>i</i>=1, &#8230;, <i>k-1,</i> <i>j</i>=2, &#8230;, <i>k</i>) for <i>i</i>&lt;<i>j</i>
    unless <i>i</i>=1 and <i>j</i>=<i>k </i>(that is the polyline does not
    contain the same pixel twice).</p>
    <p ALIGN="JUSTIFY">A <i>set of black pixels</i> <b><i>S</i></b>
    is <i>connected</i> if for each pair of pixels (<b><i>P,Q</i></b>) in <b><i>S
    </i></b>there is at least one polyline <b><i>L</i></b> between <b><i>P</i></b>
    and <b><i>Q</i></b> with all pixels of <b><i>L</i></b> belonging to <b><i>S</i></b>.</p>
    <p>A <i>component</i> of a bitmap is a maximal
    connected set of black pixels. A component may enclose <i>holes</i>. A <i>hole</i>
    consists of white pixels that are inside a closed polyline. A <i>compact
    component</i> encloses no holes.</p>
    <p>Note that in Figure 1 the white pixel in the
    middle, marked with <b><i>x,</i></b> is<b> not</b> inside the highlighted
    closed polyline.</p>
<center>
      <p><img border="0" src="0170a.gif"><img border="0" src="0170b.gif"><br>
</center>
    <p ALIGN="JUSTIFY">Figure 2 shows a bitmap with
    five components, of which two are compact ones.</p>
    <p ALIGN="JUSTIFY">You are to write a program
    that computes the total number of components and the number of compact
    components of a given coded bitmap.</p>
    <b>
    <p>Encoding.</b>    The bitmaps under investigation are coded (compressed) with the following
    method. Each row is coded with a sequence of integers <b><i>W<sub>1</sub>, B<sub>1</sub>,
    ..., W<sub>k</sub>, B<sub>k</sub></i></b>, where <b><i>W<sub>i</sub></i></b>
    is the number of consecutive white pixels, and <b><i>B<sub>i</sub></i></b>
    is the number of consecutive black pixels, respectively.</p>
    <p>For example, the code of the first line of
    the bitmap in Figure 2 is the sequence 4 7 4 4 1 0. Components 4 and 5 are
    compact, while components 1, 2 and 3 are not compact.</p>
    <h2>Input</h2>
    <p ALIGN="JUSTIFY">The first line of the file
    bitmap.in contains two positive integers, <b><i>N</i></b> and <b><i>M</i></b>.
    <b><i>N</i></b> (<b><i>2&lt;=N&lt;=10000</i></b>) is the number of rows and <b><i>M</i></b>
    (<b><i>2&lt;=M&lt;=1000</i></b>) is the number of columns of the bitmap. The
    next <b><i>N</i></b> lines contain the coded bitmap according to the
    paragraph on <i>encoding</i>. Each line terminates with <b><i>-1</i></b>.</p>
    <h2>Output</h2>
    <p ALIGN="JUSTIFY">The file bitmap.out must
    contain two lines, with a single integer in each line. The first line
    contains the number of all components and the second line contains the
    number of compact components of the input bitmap.</p>
    <h2>Example</h2>
    <table BORDER="1" CELLSPACING="1" CELLPADDING="1" WIDTH="453">
      <tr>
        <td WIDTH="72%" VALIGN="TOP">bitmap.in</td>
        <td WIDTH="28%" VALIGN="TOP">bitmap.out</td>
      </tr>
      <tr>
        <td WIDTH="72%" VALIGN="TOP">
          10 20<br>
          4 7 4 4 1 0 -1<br>
          0 4 1 4 1 4 1 1 1 3 -1<br>
          1 3 4 6 2 4 -1<br>
          0 7 9 4 -1<br>
          0 1 4 9 1 1 4 0 -1<br>
          0 1 1 3 1 8 1 5 -1<br>
          0 1 1 1 1 1 1 8 1 1 3 1 -1</br>
          0 1 1 3 1 1 3 1 2 1 1 1 3 1 -1<br>
          0 1 5 1 1 6 1 1 3 1 -1<br>
          0 7 3 4 1 1 3 1 -1</td>
        <td WIDTH="28%" VALIGN="TOP">
          5<br
          2</td>
      </tr>
    </table>
    </center>

    <h2>Grading</h2>
    <p ALIGN="JUSTIFY">If the first line of your
    output file contains the correct number of all components, then you obtain
    50% of the scores. If the second line of your output file contains the
    correct number of compact components, then you obtain an additional 50% of
    the scores.</p>
    </td>
  </tr>
</table>
</div>
</body>

</html>
